package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class SudokuSolver {

    /**
     * 回溯算法
     * 反复枚举可能的数字，然后判断这个数字是否有效，
     * 如果有效，开始枚举下一格，否则退回上一格，然后上一格继续枚举剩下的数字
     *
     * @param board board.length == 9
     *              board[i].length == 9
     *              board[i][j] 是一位数字或者 '.'
     *              题目数据 保证 输入数独仅有一个解
     */
    public void solveSudoku1(char[][] board) {
        fill1(board, 0);
    }

    private boolean fill1(char[][] board, int index){
        if (index > 80){
            return true;
        }
        int row = index / 9;
        int col = index % 9;
        char c = board[row][col];
        if (c != '.'){
            return fill1(board, index + 1);
        }
        for (int i = 0; i < 9; ++i){
            board[row][col] = (char) (i + '1');
            if (isValidSudoku(board) && fill1(board, index + 1)){
                return true;
            }
        }
        board[row][col] = '.';
        return false;
    }

    private boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxs = new int[9];
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 9; ++j){
                char c = board[i][j];
                if (c == '.'){
                    continue;
                }
                int n = 1 << (c - '0');
                if ((rows[i] & n) != 0){
                    return false;
                }
                rows[i] |= n;
                if ((cols[j] & n) != 0){
                    return false;
                }
                cols[j] |= n;
                int boxNumber = (i / 3) * 3 + (j / 3);
                if ((boxs[boxNumber] & n) != 0){
                    return false;
                }
                boxs[boxNumber] |= n;
            }
        }
        return true;
    }

    int[] rows = new int[9];
    int[] cols = new int[9];
    int[] boxes = new int[9];

    /**
     * 基本思路还是回溯，
     * 利用位图存储已经出现过的数字，在枚举过程中可以快速判断该数是否有效
     */
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 9; ++j){
                char c = board[i][j];
                if (c != '.'){
                    setValue(i, j, c - '1');
                }
            }
        }
        fill(board, 0);
    }

    public boolean fill(char[][] board, int index){
        if (index > 80){
            return true;
        }
        int row = index / 9;
        int col = index % 9;
        char c = board[row][col];
        int xor = rows[row] | cols[col] | boxes[(row / 3) * 3 + col / 3];
        if (c != '.'){
            return fill(board, index + 1);
        }
        for (int i = 0; i < 9; ++i){
            if (getBit(xor, i)){
                continue;
            }
            setValue(row, col, i);
            if (fill(board, index + 1)){
                board[row][col] = (char) (i + '1');
                return true;
            }
            clearValue(row, col, i);
        }
        return false;
    }

    public void clearValue(int i, int j, int val){
        rows[i] = clearBit(rows[i], val);
        cols[j] = clearBit(cols[j], val);
        int boxIndex = (i / 3) * 3 + j / 3;
        boxes[boxIndex] = clearBit(boxes[boxIndex], val);
    }

    public void setValue(int i, int j, int val){
        rows[i] = setBit(rows[i], val);
        cols[j] = setBit(cols[j], val);
        int boxIndex = (i / 3) * 3 + j / 3;
        boxes[boxIndex] = setBit(boxes[boxIndex], val);
    }

    private boolean getBit(int num, int index){
        return (num & (1 << index)) > 0;
    }

    private int setBit(int num, int index){
        return num | (1 << index);
    }

    private int clearBit(int num, int index){
        return num - (1 << index);
    }

    public static void main(String[] args) {
        char[][] board = ArrayUtils.parseArray("" +
                "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n" +
                ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n" +
                ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n" +
                ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n" +
                ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n" +
                ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n" +
                ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n" +
                ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n" +
                ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n" +
                "", char[].class);
        new SudokuSolver().solveSudoku(board);
        PrintUtils.println(board);
        char[][] out = ArrayUtils.parseArray("" +
                "[[\"5\",\"3\",\"4\",\"6\",\"7\",\"8\",\"9\",\"1\",\"2\"],[\"6\",\"7\",\"2\",\"1\",\"9\",\"5\",\"3\",\"4\",\"8\"],[\"1\",\"9\",\"8\",\"3\",\"4\",\"2\",\"5\",\"6\",\"7\"],[\"8\",\"5\",\"9\",\"7\",\"6\",\"1\",\"4\",\"2\",\"3\"],[\"4\",\"2\",\"6\",\"8\",\"5\",\"3\",\"7\",\"9\",\"1\"],[\"7\",\"1\",\"3\",\"9\",\"2\",\"4\",\"8\",\"5\",\"6\"],[\"9\",\"6\",\"1\",\"5\",\"3\",\"7\",\"2\",\"8\",\"4\"],[\"2\",\"8\",\"7\",\"4\",\"1\",\"9\",\"6\",\"3\",\"5\"],[\"3\",\"4\",\"5\",\"2\",\"8\",\"6\",\"1\",\"7\",\"9\"]]\n" +
                "", char[].class);
        Assert.isTrue(Arrays.deepEquals(board, out));
        PrintUtils.println(board);
    }
}
